The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(x1))))))))))
0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(0(1(2(x1)))))))))))))
0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))
0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2.
The certificate found is represented by the following graph.

Start state: 1016
Accept states: [1017]
Transitions:
1016→1017[0_1|0]
1016→1016[1_1|0, 2_1|0]
1016→1018[2_1|1]
1016→1027[2_1|1]
1016→1039[2_1|1]
1016→1054[2_1|1]
1018→1019[1_1|1]
1019→1020[0_1|1]
1020→1021[2_1|1]
1021→1022[1_1|1]
1022→1023[0_1|1]
1023→1024[1_1|1]
1024→1025[1_1|1]
1025→1026[2_1|1]
1026→1017[1_1|1]
1026→1020[1_1|1]
1026→1029[1_1|1]
1026→1041[1_1|1]
1026→1056[1_1|1]
1026→1072[2_1|2]
1026→1081[2_1|2]
1026→1093[2_1|2]
1026→1108[2_1|2]
1027→1028[1_1|1]
1028→1029[0_1|1]
1029→1030[2_1|1]
1030→1031[1_1|1]
1031→1032[0_1|1]
1032→1033[2_1|1]
1033→1034[1_1|1]
1034→1035[0_1|1]
1035→1036[1_1|1]
1036→1037[1_1|1]
1037→1038[2_1|1]
1038→1017[1_1|1]
1038→1020[1_1|1]
1038→1029[1_1|1]
1038→1041[1_1|1]
1038→1056[1_1|1]
1038→1072[2_1|2]
1038→1081[2_1|2]
1038→1093[2_1|2]
1038→1108[2_1|2]
1039→1040[1_1|1]
1040→1041[0_1|1]
1041→1042[2_1|1]
1042→1043[1_1|1]
1043→1044[0_1|1]
1044→1045[2_1|1]
1045→1046[1_1|1]
1046→1047[0_1|1]
1047→1048[2_1|1]
1048→1049[1_1|1]
1049→1050[0_1|1]
1050→1051[1_1|1]
1051→1052[1_1|1]
1052→1053[2_1|1]
1053→1017[1_1|1]
1053→1020[1_1|1]
1053→1029[1_1|1]
1053→1041[1_1|1]
1053→1056[1_1|1]
1053→1072[2_1|2]
1053→1081[2_1|2]
1053→1093[2_1|2]
1053→1108[2_1|2]
1054→1055[1_1|1]
1055→1056[0_1|1]
1056→1057[2_1|1]
1057→1058[1_1|1]
1058→1059[0_1|1]
1059→1060[2_1|1]
1060→1061[1_1|1]
1061→1062[0_1|1]
1062→1063[2_1|1]
1063→1064[1_1|1]
1064→1065[0_1|1]
1065→1066[2_1|1]
1066→1067[1_1|1]
1067→1068[0_1|1]
1068→1069[1_1|1]
1069→1070[1_1|1]
1070→1071[2_1|1]
1071→1017[1_1|1]
1071→1020[1_1|1]
1071→1029[1_1|1]
1071→1041[1_1|1]
1071→1056[1_1|1]
1071→1072[2_1|2]
1071→1081[2_1|2]
1071→1093[2_1|2]
1071→1108[2_1|2]
1072→1073[1_1|2]
1073→1074[0_1|2]
1074→1075[2_1|2]
1075→1076[1_1|2]
1076→1077[0_1|2]
1077→1078[1_1|2]
1078→1079[1_1|2]
1079→1080[2_1|2]
1080→1023[1_1|2]
1080→1032[1_1|2]
1080→1044[1_1|2]
1080→1059[1_1|2]
1080→1126[2_1|2]
1080→1135[2_1|2]
1080→1147[2_1|2]
1080→1162[2_1|2]
1081→1082[1_1|2]
1082→1083[0_1|2]
1083→1084[2_1|2]
1084→1085[1_1|2]
1085→1086[0_1|2]
1086→1087[2_1|2]
1087→1088[1_1|2]
1088→1089[0_1|2]
1089→1090[1_1|2]
1090→1091[1_1|2]
1091→1092[2_1|2]
1092→1023[1_1|2]
1092→1032[1_1|2]
1092→1044[1_1|2]
1092→1059[1_1|2]
1092→1126[2_1|2]
1092→1135[2_1|2]
1092→1147[2_1|2]
1092→1162[2_1|2]
1093→1094[1_1|2]
1094→1095[0_1|2]
1095→1096[2_1|2]
1096→1097[1_1|2]
1097→1098[0_1|2]
1098→1099[2_1|2]
1099→1100[1_1|2]
1100→1101[0_1|2]
1101→1102[2_1|2]
1102→1103[1_1|2]
1103→1104[0_1|2]
1104→1105[1_1|2]
1105→1106[1_1|2]
1106→1107[2_1|2]
1107→1023[1_1|2]
1107→1032[1_1|2]
1107→1044[1_1|2]
1107→1059[1_1|2]
1107→1126[2_1|2]
1107→1135[2_1|2]
1107→1147[2_1|2]
1107→1162[2_1|2]
1108→1109[1_1|2]
1109→1110[0_1|2]
1110→1111[2_1|2]
1111→1112[1_1|2]
1112→1113[0_1|2]
1113→1114[2_1|2]
1114→1115[1_1|2]
1115→1116[0_1|2]
1116→1117[2_1|2]
1117→1118[1_1|2]
1118→1119[0_1|2]
1119→1120[2_1|2]
1120→1121[1_1|2]
1121→1122[0_1|2]
1122→1123[1_1|2]
1123→1124[1_1|2]
1124→1125[2_1|2]
1125→1023[1_1|2]
1125→1032[1_1|2]
1125→1044[1_1|2]
1125→1059[1_1|2]
1125→1126[2_1|2]
1125→1135[2_1|2]
1125→1147[2_1|2]
1125→1162[2_1|2]
1126→1127[1_1|2]
1127→1128[0_1|2]
1128→1129[2_1|2]
1129→1130[1_1|2]
1130→1131[0_1|2]
1131→1132[1_1|2]
1132→1133[1_1|2]
1133→1134[2_1|2]
1134→1035[1_1|2]
1134→1047[1_1|2]
1134→1062[1_1|2]
1134→1180[2_1|2]
1134→1189[2_1|2]
1134→1201[2_1|2]
1134→1216[2_1|2]
1135→1136[1_1|2]
1136→1137[0_1|2]
1137→1138[2_1|2]
1138→1139[1_1|2]
1139→1140[0_1|2]
1140→1141[2_1|2]
1141→1142[1_1|2]
1142→1143[0_1|2]
1143→1144[1_1|2]
1144→1145[1_1|2]
1145→1146[2_1|2]
1146→1035[1_1|2]
1146→1047[1_1|2]
1146→1062[1_1|2]
1146→1180[2_1|2]
1146→1189[2_1|2]
1146→1201[2_1|2]
1146→1216[2_1|2]
1147→1148[1_1|2]
1148→1149[0_1|2]
1149→1150[2_1|2]
1150→1151[1_1|2]
1151→1152[0_1|2]
1152→1153[2_1|2]
1153→1154[1_1|2]
1154→1155[0_1|2]
1155→1156[2_1|2]
1156→1157[1_1|2]
1157→1158[0_1|2]
1158→1159[1_1|2]
1159→1160[1_1|2]
1160→1161[2_1|2]
1161→1035[1_1|2]
1161→1047[1_1|2]
1161→1062[1_1|2]
1161→1180[2_1|2]
1161→1189[2_1|2]
1161→1201[2_1|2]
1161→1216[2_1|2]
1162→1163[1_1|2]
1163→1164[0_1|2]
1164→1165[2_1|2]
1165→1166[1_1|2]
1166→1167[0_1|2]
1167→1168[2_1|2]
1168→1169[1_1|2]
1169→1170[0_1|2]
1170→1171[2_1|2]
1171→1172[1_1|2]
1172→1173[0_1|2]
1173→1174[2_1|2]
1174→1175[1_1|2]
1175→1176[0_1|2]
1176→1177[1_1|2]
1177→1178[1_1|2]
1178→1179[2_1|2]
1179→1035[1_1|2]
1179→1047[1_1|2]
1179→1062[1_1|2]
1179→1180[2_1|2]
1179→1189[2_1|2]
1179→1201[2_1|2]
1179→1216[2_1|2]
1180→1181[1_1|2]
1181→1182[0_1|2]
1182→1183[2_1|2]
1183→1184[1_1|2]
1184→1185[0_1|2]
1185→1186[1_1|2]
1186→1187[1_1|2]
1187→1188[2_1|2]
1188→1050[1_1|2]
1188→1065[1_1|2]
1188→1234[2_1|2]
1188→1243[2_1|2]
1188→1255[2_1|2]
1188→1270[2_1|2]
1189→1190[1_1|2]
1190→1191[0_1|2]
1191→1192[2_1|2]
1192→1193[1_1|2]
1193→1194[0_1|2]
1194→1195[2_1|2]
1195→1196[1_1|2]
1196→1197[0_1|2]
1197→1198[1_1|2]
1198→1199[1_1|2]
1199→1200[2_1|2]
1200→1050[1_1|2]
1200→1065[1_1|2]
1200→1234[2_1|2]
1200→1243[2_1|2]
1200→1255[2_1|2]
1200→1270[2_1|2]
1201→1202[1_1|2]
1202→1203[0_1|2]
1203→1204[2_1|2]
1204→1205[1_1|2]
1205→1206[0_1|2]
1206→1207[2_1|2]
1207→1208[1_1|2]
1208→1209[0_1|2]
1209→1210[2_1|2]
1210→1211[1_1|2]
1211→1212[0_1|2]
1212→1213[1_1|2]
1213→1214[1_1|2]
1214→1215[2_1|2]
1215→1050[1_1|2]
1215→1065[1_1|2]
1215→1234[2_1|2]
1215→1243[2_1|2]
1215→1255[2_1|2]
1215→1270[2_1|2]
1216→1217[1_1|2]
1217→1218[0_1|2]
1218→1219[2_1|2]
1219→1220[1_1|2]
1220→1221[0_1|2]
1221→1222[2_1|2]
1222→1223[1_1|2]
1223→1224[0_1|2]
1224→1225[2_1|2]
1225→1226[1_1|2]
1226→1227[0_1|2]
1227→1228[2_1|2]
1228→1229[1_1|2]
1229→1230[0_1|2]
1230→1231[1_1|2]
1231→1232[1_1|2]
1232→1233[2_1|2]
1233→1050[1_1|2]
1233→1065[1_1|2]
1233→1234[2_1|2]
1233→1243[2_1|2]
1233→1255[2_1|2]
1233→1270[2_1|2]
1234→1235[1_1|2]
1235→1236[0_1|2]
1236→1237[2_1|2]
1237→1238[1_1|2]
1238→1239[0_1|2]
1239→1240[1_1|2]
1240→1241[1_1|2]
1241→1242[2_1|2]
1242→1068[1_1|2]
1243→1244[1_1|2]
1244→1245[0_1|2]
1245→1246[2_1|2]
1246→1247[1_1|2]
1247→1248[0_1|2]
1248→1249[2_1|2]
1249→1250[1_1|2]
1250→1251[0_1|2]
1251→1252[1_1|2]
1252→1253[1_1|2]
1253→1254[2_1|2]
1254→1068[1_1|2]
1255→1256[1_1|2]
1256→1257[0_1|2]
1257→1258[2_1|2]
1258→1259[1_1|2]
1259→1260[0_1|2]
1260→1261[2_1|2]
1261→1262[1_1|2]
1262→1263[0_1|2]
1263→1264[2_1|2]
1264→1265[1_1|2]
1265→1266[0_1|2]
1266→1267[1_1|2]
1267→1268[1_1|2]
1268→1269[2_1|2]
1269→1068[1_1|2]
1270→1271[1_1|2]
1271→1272[0_1|2]
1272→1273[2_1|2]
1273→1274[1_1|2]
1274→1275[0_1|2]
1275→1276[2_1|2]
1276→1277[1_1|2]
1277→1278[0_1|2]
1278→1279[2_1|2]
1279→1280[1_1|2]
1280→1281[0_1|2]
1281→1282[2_1|2]
1282→1283[1_1|2]
1283→1284[0_1|2]
1284→1285[1_1|2]
1285→1286[1_1|2]
1286→1287[2_1|2]
1287→1068[1_1|2]

(2) BOUNDS(O(1), O(n^1))